/*
 * @lc app=leetcode.cn id=368 lang=typescript
 *
 * [368] 最大整除子集
 */

// @lc code=start
function largestDivisibleSubset(nums: number[]): number[] {
  const size = nums.length;
  const dp = new Array(size).fill(1);
  const preIdxs = new Array(size).fill(-1);

  nums.sort((a, b) => a - b);
  // 子集的最大长度
  let max = 1;
  // 子集最后一个元素的下标
  let preIdx = 0;

  for (let i = 1; i < size; i++) {
    for (let j = 0; j < i; j++) {
      // 保证是更长的子序列长度
      if (nums[i] % nums[j] === 0 && dp[j] + 1 > dp[i]) {
        dp[i] = dp[j] + 1;
        preIdxs[i] = j;
      }
    }
    if (dp[i] > max) {
      max = dp[i];
      preIdx = i;
    }
  }
  let result: number[] = [];
  // 通过记录的preIdx，逆推出结果
  while (preIdx !== -1) {
    result.push(nums[preIdx]);
    preIdx = preIdxs[preIdx];
  }

  return result;
}
// @lc code=end
